{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Repair Cars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: repairCars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #修车的最少时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>ranks</code>&nbsp;，表示一些机械工的 <strong>能力值</strong>&nbsp;。<code>ranks<sub>i</sub></code> 是第 <code>i</code> 位机械工的能力值。能力值为&nbsp;<code>r</code>&nbsp;的机械工可以在&nbsp;<code>r * n<sup>2</sup></code>&nbsp;分钟内修好&nbsp;<code>n</code>&nbsp;辆车。</p>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>cars</code>&nbsp;，表示总共需要修理的汽车数目。</p>\n",
    "\n",
    "<p>请你返回修理所有汽车&nbsp;<strong>最少</strong>&nbsp;需要多少时间。</p>\n",
    "\n",
    "<p><strong>注意：</strong>所有机械工可以同时修理汽车。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>ranks = [4,2,3,1], cars = 10\n",
    "<b>输出：</b>16\n",
    "<b>解释：</b>\n",
    "- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。\n",
    "- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。\n",
    "- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。\n",
    "- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。\n",
    "16 分钟是修理完所有车需要的最少时间。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>ranks = [5,1,8], cars = 6\n",
    "<b>输出：</b>16\n",
    "<b>解释：</b>\n",
    "- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。\n",
    "- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。\n",
    "- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。\n",
    "16 分钟时修理完所有车需要的最少时间。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ranks.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= ranks[i] &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= cars &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-repair-cars](https://leetcode.cn/problems/minimum-time-to-repair-cars/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-repair-cars](https://leetcode.cn/problems/minimum-time-to-repair-cars/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,3,1]\\n10', '[5,1,8]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(t: int) -> bool:\n",
    "            return sum(int(sqrt(t // r)) for r in ranks) >= cars\n",
    "\n",
    "        return bisect_left(range(ranks[0] * cars * cars), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:#二分法\n",
    "        debug=True#False#\n",
    "        #fixTime=[[r*c**2 for c in range(1,cars+1)] for r in ranks]#47/1071,超时，ranks.length <= 1e+5，cars <= 1e+6，数组过大\n",
    "        def carsum(n):#r * n**2=x 分钟内修好 n 辆，x分钟修车数n=sqrt(x/r)\n",
    "            return sum(int(sqrt(n/r)) for r in ranks)\n",
    "            res=0\n",
    "            for t in fixTime:\n",
    "                add=False\n",
    "                for j in range(len(t)):\n",
    "                    if t[j]>n:\n",
    "                        res+=j\n",
    "                        add=True\n",
    "                        break\n",
    "                if not add:res+=cars\n",
    "            return res\n",
    "        l,r=1,max(ranks)*cars**2\n",
    "        if debug:print(\"l=\",l,r)\n",
    "        if carsum(l)>=cars:\n",
    "            if debug:print(\"carsum(l)=\",carsum(l))\n",
    "            return l\n",
    "        elif carsum(r)<=cars:return r\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            sm,sm1=carsum(m),carsum(m+1)\n",
    "            if sm>=cars:r=m#m不行，m+1行\n",
    "            elif sm1<cars:l=m+1\n",
    "            elif sm<cars and sm1>=cars:\n",
    "                l=m+1\n",
    "                break\n",
    "        if debug:print(\"l=\",l,m,r)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def f(n):\n",
    "            return sum(math.floor((n / i)**0.5) for i in ranks)\n",
    "        return bisect_left(range(cars**2*min(ranks) + 1), cars, key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def valid(self,ranks,time,cars):\n",
    "        cnt = 0\n",
    "        for rank in ranks:\n",
    "            cnt += int(floor(sqrt(time/rank)))\n",
    "            if cnt>=cars:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        max_time = ranks[0]*cars**2+1\n",
    "        l = 0\n",
    "        r = max_time\n",
    "        # 找后继\n",
    "        i=0\n",
    "        while l<r:\n",
    "            i+=1\n",
    "            mid = (l+r)>>1\n",
    "            if(self.valid(ranks,mid,cars)):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def judge(cur):\n",
    "            num = 0\n",
    "            for r in ranks:\n",
    "                num += math.floor(math.sqrt(cur//r))\n",
    "                if num>=cars:\n",
    "                    return True\n",
    "            if num<cars:\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        l,r = 0, min(ranks)*cars*cars\n",
    "        ans = r\n",
    "        te = []\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if judge(mid):\n",
    "                r = mid - 1\n",
    "                ans = min(ans,mid)\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "\n",
    "        rank_pair = {}\n",
    "        for rank in ranks:\n",
    "            if rank in rank_pair:\n",
    "                rank_pair[rank] += 1\n",
    "            else:\n",
    "                rank_pair[rank] = 1\n",
    "        \n",
    "        def timeRepairCar(time: int) -> int:\n",
    "            res = 0\n",
    "            for rank, num in rank_pair.items():\n",
    "                res += int(math.sqrt(time // rank)) * num\n",
    "            # print(\"{} times repair {} cars\".format(time, res))\n",
    "            return res\n",
    "        \n",
    "        min_t = (cars // len(ranks))**2\n",
    "        max_t =(cars // len(ranks) + 1)**2 * 100\n",
    "        k = (min_t + max_t) // 2\n",
    "\n",
    "        while min_t < max_t:\n",
    "            # print(\"new test {}, min {}, max {}\".format(k, min_t, max_t))\n",
    "            res = timeRepairCar(k)\n",
    "            if res < cars:\n",
    "                min_t = k + 1\n",
    "            else:\n",
    "                max_t = k\n",
    "            k = int(math.sqrt(min_t * max_t))\n",
    "        return max_t\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        small = 0\n",
    "        large = ranks[0] * cars * cars\n",
    "\n",
    "        while (small < large):\n",
    "            t = (small + large) // 2 \n",
    "            car_sum = 0\n",
    "            for r in ranks:\n",
    "                car_sum += int((t/r) ** 0.5)\n",
    "            if car_sum >= cars:\n",
    "                large = t\n",
    "            else:\n",
    "                small = t + 1\n",
    "\n",
    "        return small\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Elem:\n",
    "    def __init__(self, rank, level):\n",
    "        self.rank = rank\n",
    "        self.level = level\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.value() < other.value()\n",
    "\n",
    "    def value(self) -> int:\n",
    "        return (self.level ** 2) * self.rank\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        pq = PriorityQueue()\n",
    "        workers = defaultdict(int)\n",
    "        for rank in ranks:\n",
    "            workers[rank] += 1\n",
    "        for key, _ in workers.items():\n",
    "            pq.put(Elem(key, 1))\n",
    "        top = None\n",
    "        while cars > 0:\n",
    "            top = pq.get()\n",
    "            cars -= workers[top.rank]\n",
    "            pq.put(Elem(top.rank, top.level + 1))\n",
    "        return top.value()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        # 二分答案?\n",
    "        # x时间内 , 计算一共能修多少车 是 O(ranks.length)\n",
    "        # 修车时间范围是 (1,1e6)\n",
    "        # 1e5 * log2(1e6)\n",
    "        n = len(ranks)\n",
    "        l, r = 1, max(100 , int(pow(int(cars/n) , 2)) * sum(ranks))\n",
    "        print(l,r)\n",
    "        def check(cost):\n",
    "            cnt = 0\n",
    "            for rank in ranks:\n",
    "                cnt += int(pow(int(cost/rank),0.5))                \n",
    "            return cnt >= cars\n",
    "        while l < r:\n",
    "            m = l + int((r-l)/2)\n",
    "            print(l,m,r)\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l, r = 0, max(ranks) * cars * cars\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "\n",
    "            s = 0\n",
    "            t = -1\n",
    "            for k in ranks:\n",
    "                n = int(sqrt(m / k))\n",
    "                s = s + n\n",
    "                t = max(t, k * n * n)\n",
    "\n",
    "            print(l, r, s,t)\n",
    "\n",
    "            if s > cars:\n",
    "                if l + 1 == r: return l\n",
    "                r = m\n",
    "            elif s < cars:\n",
    "                if l + 1 == r: return r\n",
    "                l = m\n",
    "            else:\n",
    "                return t\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(ranks, t, cars)->bool:\n",
    "            cnt = 0\n",
    "            for r in ranks:\n",
    "                cnt += int(sqrt(t/r))\n",
    "            return cnt>=cars\n",
    "\n",
    "        left, right = 0, max(ranks)*cars*cars+1\n",
    "        while left+1<right:\n",
    "            mid = (left+right)>>1\n",
    "            if check(ranks, mid, cars):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(t):\n",
    "            return sum(int((t / r)**0.5) for r in ranks) >= cars\n",
    "        \n",
    "        max_time = min(ranks) * cars ** 2\n",
    "        l = 1\n",
    "        r = max_time+1\n",
    "        while l < r:\n",
    "            mid = (l + r)//2\n",
    "            print(l, r, mid)\n",
    "            if check(mid):\n",
    "                # 时间够了，修好了足够的车\n",
    "                r = mid\n",
    "            else:\n",
    "                # 时间不够，没修好\n",
    "                l = mid + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        left = 0\n",
    "        right = min(ranks) * cars * cars\n",
    "        while left + 1 < right:  # 开区间\n",
    "            mid = (left + right) // 2\n",
    "            if sum(isqrt(mid // r) for r in ranks) >= cars:\n",
    "                right = mid  # 满足要求\n",
    "            else:\n",
    "                left = mid\n",
    "        return right  # 最小的满足要求的值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        left, right = 0, max(ranks) * cars * cars\n",
    "        while left < right:\n",
    "            mid = left + (right-left) // 2\n",
    "            cur = cars\n",
    "            for i in ranks:\n",
    "                cur -= math.floor(sqrt(mid // i))\n",
    "                if cur <= 0:\n",
    "                    break\n",
    "            if cur <= 0:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        left, right = 0, min(ranks) * cars * cars\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum(isqrt(mid // r) for r in ranks) >= cars:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(t):\n",
    "            cnt=0\n",
    "            for r in ranks:\n",
    "                n=int((t/r)**0.5)\n",
    "                cnt +=n\n",
    "            return cnt >=cars\n",
    "                \n",
    "        return bisect_left(range(1000000000000000),True,key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(t):\n",
    "            sum_cars = 0\n",
    "            for r in ranks:\n",
    "                sum_cars += floor(sqrt(t // r))\n",
    "            return sum_cars >= cars\n",
    "        left, right = 0, min(ranks) * cars * cars\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l,r=1,ranks[0]*cars*cars\n",
    "        def check(m):\n",
    "            cnt=0\n",
    "            for i in ranks:\n",
    "                cnt+=floor(sqrt(m//i))\n",
    "            return cnt>=cars\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            if check(m):\n",
    "                r=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(l):\n",
    "            return cars<=sum([int(sqrt(l/r)) for r in ranks])\n",
    "        left,right=0,(cars//len(ranks)+1)**2*max(ranks)\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                right=mid-1\n",
    "                ans=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   \n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        left = 0\n",
    "        right = min(ranks) * cars * cars\n",
    "        while left + 1 < right:  # 开区间\n",
    "            mid = (left + right) // 2\n",
    "            if sum(isqrt(mid // r) for r in ranks) >= cars:\n",
    "                right = mid  # 满足要求\n",
    "            else:\n",
    "                left = mid\n",
    "        return right  # 最小的满足要求的值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(t: int) -> bool:\n",
    "            return sum(int(sqrt(t // r)) for r in ranks) >= cars\n",
    "\n",
    "        return bisect_left(range(ranks[0] * cars * cars), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        count = collections.Counter(ranks)\n",
    "        min_r = min(list(count.keys()))\n",
    "        r = min_r*cars*cars+1\n",
    "        l =  0\n",
    "        def check(x):\n",
    "            c = 0\n",
    "            for k,v in count.items():\n",
    "                c += math.isqrt(x//k)*v\n",
    "            if c>=cars:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        #当car=0 时,结果为0\n",
    "        while l < r:\n",
    "            mid = l + (r-l)//2\n",
    "            # sum_car = sum( [int(sqrt(mid//key))*cnt for key,cnt in count.items()])\n",
    "            if check(mid): #左开右闭\n",
    "                r = mid  # 满足要求\n",
    "            else:#sum_car <car,left+1\n",
    "                l = mid+1\n",
    "        return l # 最小的满足要求的值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        def check(l):\n",
    "            return cars<=sum([int(sqrt(l/r)) for r in ranks])\n",
    "        left,right=0,(cars//len(ranks)+1)**2*max(ranks)\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            print(mid)\n",
    "            if check(mid):\n",
    "                right=mid-1\n",
    "                ans=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l = 1\n",
    "        r = ranks[0] * cars * cars\n",
    "        mid = -1\n",
    "        def check(time):\n",
    "            ans = 0\n",
    "            for i in range(len(ranks)):\n",
    "                ans += int((time / ranks[i]) ** 0.5)\n",
    "            if ans >= cars:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            #print(l, r, mid)\n",
    "            if not check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: [int], cars: int) -> int:\n",
    "        C1=Counter(ranks)\n",
    "\n",
    "        # h1=   ( (car+1)^2*r, r, cars,people)    ( 继续新增一车会变成多少，权值，每人已分配的车数，工人数）\n",
    "        # 再来 n 辆车， 该分给谁？\n",
    "        h1=[]\n",
    "        for r,peoples in C1.items():\n",
    "            h1.append([1*r,r,0,peoples])\n",
    "\n",
    "        heapq.heapify(h1)\n",
    "        leftcars=cars\n",
    "        maxtimes=-1\n",
    "        while leftcars>0:\n",
    "            data=heapq.heappop(h1)\n",
    "            tmp=data.copy()\n",
    "            data=[pow(tmp[2]+2,2)*tmp[1],tmp[1],tmp[2]+1, tmp[3]]\n",
    "            maxtimes=max(maxtimes,pow(tmp[2]+1,2)*tmp[1])\n",
    "            heapq.heappush(h1,data)\n",
    "            leftcars-=data[3]\n",
    "        return maxtimes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        import math\n",
    "        # 最慢的师傅一个人修要多久\n",
    "        max_time = math.ceil(max(ranks) * (cars )**2)\n",
    "        # 所有人都是修的最快的师傅\n",
    "        min_time = math.ceil(min(ranks) * (cars / len(ranks)) ** 2)\n",
    "        time = (min_time + max_time) // 2\n",
    "\n",
    "        def Divede(left, right, time):\n",
    "            if left == right:\n",
    "                return time\n",
    "            can_fix = 0\n",
    "            for rank in ranks:\n",
    "                can_fix += math.floor(math.sqrt(time / rank))\n",
    "            if can_fix >= cars:\n",
    "                right = time\n",
    "                time = (left + right) // 2\n",
    "                return Divede(left, right, time)\n",
    "            elif can_fix < cars:\n",
    "                left = time + 1\n",
    "                time = (left + right) // 2\n",
    "                return Divede(left, right, time)\n",
    "        return Divede(min_time, max_time, time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        import math\n",
    "        # 所有人都是修的最慢的师傅\n",
    "        max_time = math.ceil(max(ranks) * (cars )**2)\n",
    "        # 所有人都是修的最快的师傅\n",
    "        min_time = math.ceil(min(ranks) * (cars / len(ranks)) ** 2)\n",
    "        time = (min_time + max_time) // 2\n",
    "\n",
    "        def Divede(left, right, time):\n",
    "            if left == right:\n",
    "                return time\n",
    "            can_fix = 0\n",
    "            for rank in ranks:\n",
    "                can_fix += math.floor(math.sqrt(time / rank))\n",
    "            if can_fix >= cars:\n",
    "                right = time\n",
    "                time = (left + right) // 2\n",
    "                return Divede(left, right, time)\n",
    "            elif can_fix < cars:\n",
    "                left = time + 1\n",
    "                time = (left + right) // 2\n",
    "                return Divede(left, right, time)\n",
    "        return Divede(min_time, max_time, time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        c=len(ranks)\n",
    "        y=cars%c\n",
    "        t=(int)((cars-y)/c)\n",
    "        print(c,y,t)\n",
    "        mi=ranks[0]\n",
    "        ma=ranks[0]\n",
    "        for i in ranks:\n",
    "            if mi>i:\n",
    "                mi=i\n",
    "            if ma<i:\n",
    "                ma=i\n",
    "        print(ma,mi)\n",
    "        ret=mi*(y+t)*(y+t)\n",
    "        x=ma*t*t\n",
    "        if ret<x:\n",
    "            ret=x\n",
    "        print(ret)    \n",
    "        def dwjs(x:int,y:int)->int:\n",
    "            if x+1==y:\n",
    "                return y\n",
    "            h=x+y \n",
    "            h=(int)((h-h%2)/2)\n",
    "            print('H',x,y,h)\n",
    "            \n",
    "            i=0\n",
    "            j=0\n",
    "            for i in ranks:\n",
    "                j+=int(sqrt(h/i))\n",
    "                if j>=cars:\n",
    "                    return dwjs(x,h)\n",
    "            return dwjs(h,y)   \n",
    "\n",
    "        return dwjs(0,ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        @cache\n",
    "        def sig(time,i):\n",
    "            now=int(int(time/i)**0.5)\n",
    "            return now\n",
    "        ranks.sort()\n",
    "        time=ranks[0]*cars*cars\n",
    "        l=time//2\n",
    "        while l>=0.1:\n",
    "            now=0\n",
    "            for i in ranks[:-1]:\n",
    "                now=now+sig(time,i)\n",
    "            print(now)\n",
    "            if ranks[-1]*(cars-now)**2>time and cars>now:\n",
    "                time=time+l\n",
    "            else:\n",
    "                time=time-l\n",
    "            l=l/2\n",
    "            print(time,l)\n",
    "        return int(time+0.5)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        if len(ranks) == 1:\n",
    "            return ranks[0] * cars * cars\n",
    "        \n",
    "        @cache\n",
    "        def cul(x, i):\n",
    "            return int(sqrt(x // i))\n",
    "\n",
    "        left, right = 0, cars ** 2 * max(ranks) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum(cul(mid, r) for r in ranks) >= cars:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        @cache\n",
    "        def sig(time,i):\n",
    "            now=int(int(time/i)**0.5)\n",
    "            return now\n",
    "        ranks.sort()\n",
    "        time=ranks[0]*cars*cars\n",
    "        l=time//2\n",
    "        while l>=0.1:\n",
    "            now=0\n",
    "            for i in ranks[:-1]:\n",
    "                now=now+sig(time,i)\n",
    "            print(now)\n",
    "            if ranks[-1]*(cars-now)**2>time and cars>now:\n",
    "                time=time+l\n",
    "            else:\n",
    "                time=time-l\n",
    "            l=l/2\n",
    "            print(time,l)\n",
    "        return int(time+0.5)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from bisect import bisect_right,insort_left,bisect_left\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        s = lambda x : sum([int(math.sqrt(x/r)) for r in ranks])\n",
    "        return bisect_left(range(min(ranks) *cars*cars),cars,key=s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        \n",
    "        def is_done(time):\n",
    "            fix = sum([int(math.sqrt(time/rank)) for rank in ranks])\n",
    "            return fix >= cars\n",
    "        \n",
    "        l, r = 0, ranks[0] * cars ** 2\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if is_done(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        s = lambda t: sum([int(sqrt(t//r)) for r in ranks])\n",
    "        return bisect_left(range(min(ranks)*cars*cars), cars, key=s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "\n",
    "        def check(t: int) -> bool:\n",
    "            return sum([int(math.sqrt(t // r)) for r in ranks]) >= cars\n",
    "\n",
    "        # Lower bound.\n",
    "        left, right = 0, min(ranks) * cars * cars\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心，要进尽可能多修\n",
    "# 最少， 二分法\n",
    "import math\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l, r = 1, min(ranks) * cars * cars\n",
    "\n",
    "        def check(t):\n",
    "            s = sum([floor(math.sqrt(t/r)) for r in ranks])\n",
    "            if s >= cars:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        while l < r:\n",
    "            m = (l+r) // 2\n",
    "            if check(m): \n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        # sum(xi) = cars, min(xi ** 2 * ri)\n",
    "        l, r = 0, max(ranks) * cars ** 2\n",
    "        while l + 1 < r:\n",
    "            m = (l + r + 1) // 2\n",
    "            if sum([int((m / r) ** 0.5) for r in ranks]) >= cars:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        \n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l,r = 0,cars*cars*min(ranks)\n",
    "        while l<=r:\n",
    "            m = l+(r-l)//2\n",
    "            res = sum([int(sqrt(m//x)) for x in ranks])\n",
    "            if res < cars: l = m+1\n",
    "            else: r = m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        # max_time = max(ranks) * cars * cars\n",
    "        n = len(ranks)\n",
    "        l,r = 0, max(ranks) * cars * cars\n",
    "        while(l <= r):\n",
    "            m = (l + r) >> 1\n",
    "            if sum([int((m / repair) ** 0.5) for repair in ranks]) >= cars:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l , r = 1, ranks[0] * cars * cars\n",
    "        def check(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l , r = 1, ranks[0] * cars * cars\n",
    "        def check(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        return bisect_left(range(10 ** 15), True, key=lambda t: sum([int((t / r)**0.5) for r in ranks]) >= cars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        return bisect_left(range(10 ** 15), True, key=lambda t: sum([floor(sqrt(t / r)) for r in ranks]) >= cars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l , r = 1, ranks[0] * cars * cars\n",
    "        def check(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l,r=1,max(ranks)*cars*cars+1\n",
    "        res = max(ranks)*cars*cars\n",
    "        while l<r:\n",
    "            m = (l+r)//2\n",
    "            cur_cars = [math.floor(math.sqrt(m/rank)) for rank in ranks]\n",
    "            cur_cars = sum(cur_cars)\n",
    "            if cur_cars>=cars:\n",
    "                res = min(res,m)\n",
    "                r=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l,r = 1,ranks[0]*cars*cars\n",
    "        def check(m):\n",
    "            return sum([floor(sqrt(m//x)) for x in ranks])>=cars\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if check(m):\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        left,right=1,ranks[0]*cars*cars\n",
    "        def check(m):\n",
    "            return sum([floor(sqrt(m//x)) for x in ranks]) >=cars\n",
    "        while left<right:\n",
    "            mid=left+right>>1\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l, r = 1, ranks[0] * cars * cars\n",
    "        def check(m):\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "\n",
    "        return l \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l , r = 1, max(ranks) * cars * cars\n",
    "        def check(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l , r = 1, ranks[0] * cars * cars\n",
    "\n",
    "        def canRepair(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "    \n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if canRepair(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        l,r=1,ranks[0]*cars*cars\n",
    "        def check(m: int):\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            if check(m):\n",
    "                r=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def repairCars(self, ranks: List[int], cars: int) -> int:\n",
    "        # l = int(min(ranks) * (cars / len(ranks)) ** 2)\n",
    "        # r = math.ceil(max(ranks) * (cars / len(ranks)) ** 2)\n",
    "        # while l < r:\n",
    "        #     m = (l + r) >> 1\n",
    "        #     max_fix = sum([int(math.sqrt(m//x)) for x in ranks])\n",
    "        #     if max_fix >= cars:\n",
    "        #         r = m\n",
    "        #     else:\n",
    "        #         l = m + 1\n",
    "\n",
    "        # return l\n",
    "\n",
    "        l , r = 1, ranks[0] * cars * cars\n",
    "        def check(m: int) -> bool:\n",
    "            return sum([floor(sqrt(m // x)) for x in ranks]) >= cars\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
